package com.singzi.leetcode.jianzhiOffer;

public class T0004 {

    public static void main(String[] args) {
        Solution0004 solution0004 = new Solution0004();
        int [][]matrix = {
                {0,2,3,4,41},
                {1,2,3,4,55},
                {1,2,33,4,56},
                {1,2,3,4,59},
                {1,2,3,4,60},
                {1,2,3,4,88},
        };
        System.out.println(solution0004.findNumberIn2DArray(matrix, 100));
    }
}
class Solution0004 {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m-1;
        int mid;
        while (left <= right){
            mid = left + (right-left)/2;
            if(matrix[mid][0]>target){
                right = mid - 1;
            }else if(matrix[mid][0]<target){
                left = mid+1;
            }else {
                return true;
            }
        }
        System.out.println(left);
        int indexRow, indexCol;
        if(left<m && matrix[left][0]>target) indexRow = right;
        else indexRow = left-1;
        left = 0;
        right = n-1;
        while (left <= right){
            mid = left + (right-left)/2;
            if(matrix[0][mid]>target){
                right = mid - 1;
            }else if(matrix[0][mid]<target){
                left = mid+1;
            }else {
                return true;
            }
        }
        if(left<n && matrix[0][left]>target) indexCol = left;
        else indexCol = left-1;
        System.out.println(indexRow);
        System.out.println(indexCol);
        for (int i = 0; i <= indexRow; i++) {
            left = 0;
            right = indexCol;
            while (left <= right){
                mid = left + (right-left)/2;
                if(matrix[i][mid]>target){
                    right = mid - 1;
                }else if(matrix[i][mid]<target){
                    left = mid+1;
                }else {
                    return true;
                }
            }
        }

        return false;
    }
}